package com.wzh.test;

import java.util.ArrayList;
import java.util.Stack;

public class HanoiTowerDemo {
    public static int account = 0;
    public static void main(String[] args) {
        //定义三个栈A、B、C
        //每个栈下面的数字都要比上面的数字大
        ArrayList arrayListA = new ArrayList<Integer>();
        ArrayList arrayListB = new ArrayList<Integer>();
        ArrayList arrayListC = new ArrayList<Integer>();
        for(int i = 5; i >= 1;i--){
            add(arrayListA,i);
        }
        //printStack(arrayListA);
        System.out.println("=========开始挪动=============");
        move(arrayListA,arrayListC,arrayListB,arrayListA.size());
        printStack(arrayListA);
        printStack(arrayListB);
        printStack(arrayListC);
        System.out.println("account=" + account);



    }

    public static void move(ArrayList<Integer> source,ArrayList<Integer> target,ArrayList<Integer> another,int i){
        if(i == 1){
            Integer num = source.get(source.size() - 1);
            source.remove(source.size() - 1);
            add(target,num);
            account++;
        }else{
            move(source,another,target,i-1);
            move(source,target,another,1);
            move(another,target,source,i-1);
        }

//        int num1 = source.pop();
//        System.out.println("num1----A------>B");
//        another.push(num1);
//        int num2 = source.pop();
//        System.out.println("num2----A------>C");
//        target.push(num2);
//        int num3 = another.pop();
//        System.out.println("num1-----B------C");
//        target.push(num3);
//        System.out.println("结束");


    }

    public static void printStack(ArrayList<Integer> arrayList){
        for (int i = arrayList.size() -1; i >= 0; i--) {
            System.out.println(arrayList.get(i));
        }
    }

    public static void add(ArrayList<Integer> arrayList,int num){
        //必须保证所push的数据小于stack中最小的数据

        if(arrayList.size() == 0 || num < arrayList.get(arrayList.size()-1)){
            arrayList.add(num);
        }else{
            throw new RuntimeException("添加的数据大于了栈中数据");
        }
    }
}
